﻿#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>
#include<string>
#include<set>
#include<map>
using namespace std;



//void test_set1()
//{
//	// 查找在不在
//	// 排序 + 去重
//	set<int> s;
//	s.insert(5);
//	s.insert(2);
//	s.insert(6);
//	s.insert(1);
//	s.insert(1);
//	s.insert(2);
//
//	auto ret1 = s.insert(5);
//	cout << ret1.second << endl;
//
//	pair<set<int>::iterator, bool> ret2 = s.insert(5);
//	cout << ret2.second << endl;
//
//	set<int>::iterator it = s.begin();
//	while (it != s.end())
//	{
//		//*it = 10;
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 删除存在的
//	s.erase(2);
//
//	//set<int>::iterator it = s.find(3);
//	it = s.find(30);
//	if (it != s.end())
//	{
//		s.erase(it);
//	}
//
//	if (s.count(3))
//	{
//		cout << "3在" << endl;
//	}
//	else
//	{
//		cout << "3不在" << endl;
//	}
//
//	// 删除不存在的
//	s.erase(3);
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//
//
//
//void test_set2()
//{
//	std::set<int> myset;
//	std::set<int>::iterator itlow, itup;
//
//	for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
//
//
//	//itlow = myset.lower_bound(30);              //
//	itlow = myset.lower_bound(25);                // >= val值位置的iterator
//	itup = myset.upper_bound(70);                 // >  val值位置的iterator
//
//	// [25, 70]
//	myset.erase(itlow, itup);                     // 10 20 70 80 90
//
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//void test_set3()
//{
//	std::set<int> myset;
//
//	for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50
//
//	//std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
//	auto ret = myset.equal_range(30);
//
//	std::cout << "the lower bound points to: " << *ret.first << '\n';   // >= val  //30
//	std::cout << "the upper bound points to: " << *ret.second << '\n';  // > val   //40
//}
//
//
//void test_set4()
//{
//	// 排序
//	multiset<int> s;
//	s.insert(5);
//	s.insert(2);
//	s.insert(6);
//	s.insert(1);
//	s.insert(1);
//	s.insert(2);
//	s.insert(1);
//	s.insert(5);
//	s.insert(2);
//
//
//	// [>=val, >val)
//	pair<multiset<int> ::iterator, multiset<int> ::iterator> ret = s.equal_range(2);
//	s.erase(ret.first, ret.second);
//	size_t n = s.erase(2);
//	cout << n << endl;
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//
//void test_map1()
//{
//	map<string, string> dict;
//	dict.insert(pair<string, string>("sort", "排序"));
//	dict.insert(pair<string, string>("insert", "插入"));
//	dict.insert(pair<const char*, const char*>("left", "左边"));
//
//	dict.insert(make_pair("right", "右边")); // 推荐这个
//
//	dict["erase"];  // 插入
//	cout << dict["erase"] << endl; // 查找
//	dict["erase"] = "删除"; // 修改
//	cout << dict["erase"] << endl;// 查找
//	dict["test"] = "测试";  // 插入+修改
//	dict["left"] = "左边、剩余"; // 修改
//
//
//
//	// 
//	string s1("xxx"), s2("yyy");
//	dict.insert(make_pair(s1, s2));
//
//	map<string, string>::iterator it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << (*it).first << ":" << (*it).second << endl;
//		cout << it.operator->()->first << ":" << it.operator->()->second << endl;
//		cout << it->first << ":" << it->second << endl;
//
//		++it;
//	}
//	cout << endl;
//
//	for (auto& kv : dict)
//	{
//		// kv.first += 'x';
//		kv.second += 'x';
//
//		cout << kv.first << ":" << kv.second << endl;
//	}
//}
//
//void test_map2()
//{
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//	// 21:13继续
//	//for (auto& str : arr)
//	//{
//	//	//auto ret = countMap.find(str);
//	//	//if (ret == countMap.end())
//	//	//{
//	//	//	// 么有表示第一次出现，插入
//	//	//	countMap.insert(make_pair(str, 1));
//	//	//}
//	//	//else
//	//	//{
//	//	//	// 次数++
//	//	//	ret->second++;
//	//	//}
//	//	countMap[str]++;
//	//}
//
//	for (auto& str : arr)
//	{
//		countMap[str]++;
//	}
//
//	for (auto& kv : countMap)
//	{
//		cout << kv.first << ":" << kv.second << endl;
//	}
//}
//
//int main()
//{
//	//test_set1();
//	//test_set2();
//	//test_set3();
//	test_set4();
//	//test_map1();
//	system("pause");
//}
//
//
//
////1658. 将 x 减到 0 的最小操作数
//class Solution {
//public:
//	int minOperations(vector<int>& nums, int x) {
//		int sum = 0;
//		int len = nums.size();
//
//		for (auto y : nums)
//		{
//			sum += y;
//		}
//		sum = sum - x;
//		if (sum < 0) return -1;
//		int left = 0;
//		int tmp = 0;
//		int res = -1;
//		for (int right = 0; right < len; right++)
//		{
//			tmp += nums[right];
//			while (tmp > sum)
//			{
//				tmp -= nums[left++];
//			}
//			if (tmp == sum)
//			{
//				res = max(res, right - left + 1);
//			}
//		}
//		if (res == -1) return -1;
//		else return len - res;
//	}
//};
//
//
//
////904. 水果成篮
//class Solution {
//public:
//	int totalFruit(vector<int>& f) {
//		int res = 0;
//		int len = f.size();
//		unordered_map<int, int> mp;
//		for (int i = 0; i < len; i++)
//		{
//			for (int j = i; j < len; j++)
//			{
//				mp[f[j]]++;
//				if (mp.size() > 2)
//				{
//					mp.clear();
//					break;
//				}
//				res = max(res, j - i + 1);
//			}
//		}
//		return res;
//	}
//};
//
//
//class Solution {
//public:
//	int totalFruit(vector<int>& f) {
//		int res = 0;
//		unordered_map<int, int> mp;
//
//		for (int left = 0, right = 0; right < f.size(); right++)
//		{
//			mp[f[right]]++;
//			while (mp.size() > 2)
//			{
//				mp[f[left]]--;
//				if (mp[f[left]] == 0)
//				{
//					mp.erase(f[left]);
//				}
//				left++;
//			}
//			res = max(res, right - left + 1);
//		}
//
//		return res;
//	}
//};
//
//
//class Solution {
//public:
//	int totalFruit(vector<int>& f) {
//		int res = 0;
//		int hash[100001] = { 0 };
//
//		for (int left = 0, right = 0, kind = 0; right < f.size(); right++)
//		{
//			if (hash[f[right]] == 0)
//				kind++;
//			hash[f[right]]++;
//			while (kind > 2)
//			{
//				hash[f[left]]--;
//				if (hash[f[left]] == 0)
//				{
//					kind--;
//				}
//				left++;
//			}
//			res = max(res, right - left + 1);
//		}
//
//		return res;
//	}
//};




//438. 找到字符串中所有字母异位词
#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

#include<iostream>
#include<vector>
#include<string>
using namespace std;
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        int hash1[27] = { 0 };
//        vector<int> vv;
//        for (auto& x : p)
//            hash1[x - 'a']++;
//
//        int len = s.size();
//        int hash2[27] = { 0 };
//
//        int m = p.size();
//
//        for (int left = 0, right = 0; right < len; right++)
//        {
//            hash2[s[right] - 'a']++;
//
//            if (right - left + 1 > m)
//            {
//                hash2[s[left] - 'a']--;
//                left++;
//            }
//            if (right - left + 1 == m)
//            {
//                bool flag = true;
//                for (int i = 0; i < 26; i++)
//                {
//                    if (hash1[i] != hash2[i])
//                    {
//                        flag = false;
//                        break;
//                    }
//                }
//                if (flag)
//                    vv.push_back(left);
//            }
//        }
//
//        return vv;
//    }
//};


class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;
        int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
        for (auto ch : p) hash1[ch - 'a']++;
        int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
        int m = p.size();
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if (right - left + 1 > m) // 判断
            {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            // 更新结果
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};
int main(int argc, char** argv) {
    Solution().findAnagrams("defgabcd", "abc");
    return 0;
}